Search for: All records

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulationXon a directed graphGinto weighted source-to-sink paths whose weighted sum equalsX. We show that, for acyclic graphs, considering thewidthof the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stablegraphs, for which a popular heuristic is aO(logVal(X))-approximation (Val(X) being the total flow ofX), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\)to Ω (m/logm) for sparse graphs, wheremis the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X‖ being the maximum absolute value ofXon any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version. 

Despite the long history of genome assembly research, there remains a large gap between the theoretical and practical work. There is practical software with little theoretical underpinning of accuracy on one hand and theoretical algorithms which have not been adopted in practice on the other. In this paper we attempt to bridge the gap between theory and practice by showing how the theoretical safe-and-complete framework can be integrated into existing assemblers in order to improve contiguity. The optimal algorithm in this framework, called the omnitig algorithm, has not been used in practice due to its complexity and its lack of robustness to real data. Instead, we pursue a simplified notion of omnitigs (simple omnitigs), giving an efficient algorithm to compute them and demonstrating their safety under certain conditions. We modify two assemblers (wtdbg2 and Flye) by replacing their unitig algorithm with the simple omnitig algorithm. We test our modifications using real HiFi data from the D. melanogaster and the C. elegans genomes. Our modified algorithms lead to a substantial improvement in alignment-based contiguity, with negligible additional computational costs and either no or a small increase in the number of misassemblies. 

BackgroundIn extant ecosystems, complex networks of ecological interactions between organisms can be readily studied. In contrast, understanding of such interactions in ecosystems of the geologic past is incomplete. Specifically, in past terrestrial ecosystems we know comparatively little about plant biotic interactions besides saprotrophy, herbivory, mycorrhizal associations, and oviposition. Due to taphonomic biases, epiphyte communities are particularly rare in the plant-fossil record, despite their prominence in modern ecosystems. Accordingly, little is known about how terrestrial epiphyte communities have changed across geologic time. Here, we describe a tinyin situfossil epiphyte community that sheds light on plant-animal and plant-plant interactions more than 50 million years ago. MethodsA single silicifiedTodea(Osmundaceae) rhizome from a new locality of the early Eocene (ca. 52 Ma) Tufolitas Laguna del Hunco (Patagonia, Argentina) was studied in serial thin sections using light microscopy. The community of organisms colonizing the tissues of the rhizome was characterized by identifying the organisms and mapping and quantifying their distribution. A 200 × 200 µm grid was superimposed onto the rhizome cross section, and the colonizers present at each node of the grid were tallied. ResultsPreservedin situ, this community offers a rare window onto aspects of ancient ecosystems usually lost to time and taphonomic processes. The community is surprisingly diverse and includes the first fossilized leafy liverworts in South America, also marking the only fossil record of leafy bryophyte epiphytes outside of amber deposits; as well as several types of fungal hyphae and spores; microsclerotia with possible affinities in several ascomycete families; and evidence for oribatid mites. DiscussionThe community associated with the Patagonian rhizome enriches our understanding of terrestrial epiphyte communities in the distant past and adds to a growing body of literature on osmundaceous rhizomes as important hosts for component communities in ancient ecosystems, just as they are today. Because osmundaceous rhizomes represent an ecological niche that has remained virtually unchanged over time and space and are abundant in the fossil record, they provide a paleoecological model system that could be used to explore epiphyte community structure through time.